package org.magi.sort;

import org.magi.Utils;

/**
 * 归并排序 1.0 2022.6.13
 */
public class MergeSort implements Sort{

    @Override
    public int[] sort(int[] arr) {
        if (arr == null) { return null;}
        return doSort(arr);
    }

    private int[] doSort(int[] arr) {
        if (arr.length <= 2) {
            if (arr.length == 2 && arr[0] > arr[1]) {
                Utils.switchPos(arr, 0, 1);
            }
            return arr;
        }
        int mid = arr.length / 2;
        int[] left = new int[mid];
        System.arraycopy(arr, 0, left, 0, left.length);
        int[] right = new int[arr.length - mid];
        System.arraycopy(arr, mid, right, 0, right.length);
        int[] sortedLeft = doSort(left);
        int[] sortedRight = doSort(right);

        return merge(arr, sortedLeft, sortedRight);
    }

    /**
     * 3指针逆序合并两个有序数组
     * 将sortedLeft和sortedRight合并到arr,
     * arr长度必须等于sortedLeft和sortedRight长度之和
     */
    private int[] merge(int[] arr, int[] sortedLeft, int[] sortedRight) {
        System.arraycopy(sortedLeft, 0, arr, 0, sortedLeft.length);
        int l = sortedLeft.length - 1;
        int r = sortedRight.length - 1;
        for (int i = arr.length - 1; i >= 0; i--) {
            if (r < 0) {
                break;
            }
            if (l < 0) {
                arr[i] = sortedRight[r];
                r--;
                continue;
            }
            if (arr[l] > sortedRight[r]) {
                arr[i] = arr[l];
                l--;
            } else {
                arr[i] = sortedRight[r];
                r--;
            }
        }
        return arr;
    }
}
